package com.ls.que81_85;

import java.util.Stack;

/**
 * @author ：ls
 * @date ：2022/3/5 11:22
 * @description：...
 */
public class MaximalRectangle {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int max_area = 0, val = 0, left_index=-1;
        for (int i=1; i<heights.length; i++){
            while (!stack.empty() && heights[i] < heights[stack.peek()]){
                val = heights[stack.pop()];
                while (!stack.empty() && val == heights[stack.peek()]){
                    stack.pop();
                }
                if (stack.empty()){
                    left_index = -1;
                }else {
                    left_index = stack.peek();
                }
                max_area = Math.max(max_area, (i - left_index - 1) * val);
            }
            stack.push(i);
        }
        val = heights[stack.pop()];
        while (!stack.empty()){
            max_area = Math.max(max_area, (heights.length - 1 - stack.peek()) * val);
            val = heights[stack.pop()];
        }
        max_area = Math.max(max_area, val * heights.length);
        return max_area;
    }

    public static int maximalRectangle(char[][] matrix) {
        int i, j, max_area=0, area=0;
        if (matrix.length == 0)
            return 0;
        int[][] records = new int[matrix.length][matrix[0].length];
        for (i=0;i < matrix.length; i++){
            for (j=0;j<matrix[0].length;j++){
                if (matrix[i][j] == '0')
                    continue;
                records[i][j] = j==0?1:records[i][j-1]+1;
            }
        }

        int[][] inv = new int[matrix[0].length][matrix.length];
        for (i=0;i < matrix.length; i++){
            for (j=0;j<matrix[0].length;j++){
                inv[j][i] = records[i][j];
            }
        }

        for (i=0; i<inv.length;i++){
            area = largestRectangleArea(inv[i]);
            max_area = Math.max(max_area, area);
        }
        return max_area;
    }

    public static void main(String[] args) {
        char[][] matrix = new char[][]{{'1','0','1','0','0'}, {'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        System.out.println(maximalRectangle(matrix));
    }
}
